昨天介紹完兩個排序法,今天介紹資料結構,也會配上例題(堆在刷題的時候很常用)
直接看程式
//左右子葉要是heap結構(從子葉開始heapify)
void heapify(vector<int>& arr, int root, int len){
int l = 2*root;
int r = 2*root+1;
int max_node = -1;
//若根節點已經是最大
if(l<=len&&arr[l]>arr[root]){
max_node = l;
}
else{
max_node = root;
}
if(r<=len&&arr[r]>arr[max_node]){
max_node = r;
}
if(root!=max_node){
swap(arr[max_node], arr[root]);
heapify(arr, max_node, len); //此時arr[root]是子節點
}
}
有了heapify這個操作之後,可以把數組建成堆的形式,那就可以拿來排序~~
void build_heap(vector<int>& arr){
//先建好heap結構
arr.insert(arr.begin(), 0);
for (int i = arr.size()/2; i >= 1 ; i--) { //必須要從子葉開始heapify
heapify(arr, i, arr.size()-1);
}
}
解決有些問題時,會使用不同型態或自定義的型態,例如天際線問題,就會寫成這種functor
class event_cmp{
public:
bool operator()(bd_event A, bd_event B){
if(B.x < A.x){
return true;
}
if(B.x==A.x){
if(A.cover){
return true;
}
}
return false;
}
};
priority_queue<bd_event, vector<bd_event>, event_cmp> events;
215. 数组中的第K个最大元素
這題調用堆結構的話就很直觀了~~
1878. 矩阵中最大的三个菱形和
爆搜然後放入堆~~
class Solution {
priority_queue<int> res;
int mmin = INT_MAX;
public:
vector<int> getBiggestThree(vector<vector<int>>& grid) {
int M = grid.size();
int N = grid[0].size();
vector<int> ans;
for(int i = 0; i<M; ++i){
for(int j = 0; j<N; ++j){
find(grid, i, j);
}
}
unordered_map<int, int> hash;
while(!res.empty()&&ans.size()<3){
if(!hash.count(res.top()) ){
ans.push_back(res.top());
}
hash[res.top()]++;
res.pop();
}
return ans;
}
void find(vector<vector<int>>& grid, int i, int j){
int M = grid.size();
int N = grid[0].size();
int k = 1; //邊長是k+1
int ssum = 0;
if(res.size()<=3||grid[i][j]>mmin){
res.push(grid[i][j]);
if(grid[i][j]<mmin){
mmin = grid[i][j];
}
}
const int dir_i[]{1, 1, -1, -1};
const int dir_j[]{-1, 1, 1, -1};
int ori_i = i;
int ori_j = j;
while(k){
for(int m = 0; m<4; ++m){ //四個方向
for(int n = 0; n<k; ++n){ //邊長擴展
//cout<< i<<" "<<j<<" "<<endl;
ssum+=grid[i][j];
int next_i = i+dir_i[m];
int next_j = j+dir_j[m];
if(next_i>=M||next_i<0||next_j>=N||next_j<0){
return;
}
i = next_i;
j = next_j;
}
}
if(res.size()<=3||ssum>mmin){
res.push(ssum);
if(ssum<mmin){
mmin = ssum;
}
}
ssum = 0;
i = ori_i;
j = ori_j;
k++;
}
}
};